package leetcode.code1457;

import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

import leetcode.IDebug;

public class Solution implements IDebug {

	int ans;

	public int pseudoPalindromicPaths(TreeNode root) {
		if (root.left == null && root.right == null) {
			return 1;
		}
		ans = 0;
		this.f(root, 0);
		return ans;
	}

	private void f(TreeNode root, int sum) {
		sum ^= 1 << root.val;
		if (root.left == null && root.right == null) {
			if (Integer.bitCount(sum) < 2) {
				ans++;
			}
			return;
		}
		if (root.left != null)
			this.f(root.left, sum);
		if (root.right != null)
			this.f(root.right, sum);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		int ans = this
				.pseudoPalindromicPaths(TreeArray.array2tree(H.str2array4("[2,1,1,1,3,null,null,null,null,null,1]")));
		System.out.println(ans);
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
